package com.topView2;

import java.rmi.UnexpectedException;

/**
 * @Author: huangzhigao
 * @Date: 2023/2/12 14:06
 */
public class leecode28 {
    public int strStr(String haystack, String needle) {
        int m = haystack.length();
        int n = needle.length();

        String original = " " + haystack;
        String target = " " + needle;
        char[] originalArr = original.toCharArray();
        char[] targetArr = target.toCharArray();
        int[] next = new int[n + 1];
        for (int i = 2, j = 0; i <= n; i++) {
            while (j > 0 && targetArr[i] != targetArr[j + 1]) {
                j = next[j];
            }
            if (targetArr[i] == targetArr[j + 1]) {
                j++;
            }
            next[i] = j;
        }

        for (int i = 1, j = 0; i <= m; i++) {
            while (j > 0 && originalArr[i] != targetArr[j + 1]) {
                j = next[j];
            }
            if (originalArr[i] == targetArr[j+1]) {
                j++;
            }
            if (j == n) {
                return i - n;
            }
        }
        return -1;
    }


}
